package Queue.leetcode;

import java.util.HashSet;

/**
 * 1. 问题描述
 *      我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 *
 * 2. 算法分析
 *      分析：
 *          首先什么是丑数，由题意可知所谓你的丑数指的是只包含素因子2,3,5的整数，我们需要找到从小到大
 *          找到第n个丑数
 *          由于丑数只包含素因子2,3,5，换句话说丑数是有2,3,5组成的 形如2a*3b*5c这样的形式，此外我们
 *          还注意到假设A[0]*A[1]*A[2]...*A[n]为丑数，其中每一个A[i]属于{2,3,5}，则对该式子进行变
 *          形(A[0]*...*A[n-1])*A[n],表明A[0]*...*A[n-1]也是丑数，也就是说第n个丑数是由前面的一个
 *          丑数*{2,3,5}得来的（注意上述的2*a表示的是指数形式，不是乘法）
 *          我们先找出一些丑数来看看规律
 *              1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40，假设当前不考虑1，我们看看这些丑数
 *              的规律
 *              2*1  2*2  2*3  2*4   2*5   2*6  2*8  2*9  2*10  2*12  2*15
 *              3*1  3*2  3*3  3*4   3*5   3*6  3*8  3*9
 *              5*1  5*2  5*3  5*4   5*5   5*6  5*8  5*9
 *          分析上述可以所有的丑数可以由如下的三个集合的并生成：
 *              {2*1,2*2,2*3,2*4,2*5,2*6,2*8,2*9,,,,,,}  2*10,2*12,2*15,2*16,2*18,2*20
 *              {3*1,3*2,3*3,3*4,3*5,3*6,3*8,3*9,,,,,,}
 *              {5*1,5*2,5*3,5*4,5*5,5*6,5*8,5*9,,,,,,}
 *          解析：由2,3,5我们可以凑出来的单因子由2,3,2*2,5,2*3,2*2*2,3*3 即2,3,4,5,6,8,9没有7
 *
 *          下面我们的想法就是对上述三个集合按照元素值从小到大的顺序排列
 *          首先每个集合都是按照从下到大的顺序排列的，但是没饿集合与集合之间的顺序是没有单调性的
 *          最开始2*1一定是最小的，其次我们看看2*2，此时我们需要将该元素与其他两个集合当前的最小值比较
 *          发现3*1最小，下一次从3*2开始
 *
 *    具体的比较方式：
 *      我们采用动态规划的方式来求出第i个最小的丑数，设置dp数组，其中dp[i]表示第i个最小的丑数，此外我们设置
 *      三个指针a,b,c分别初始化为0，指向上述的三个集合 dp[0] = 1
 *               {2*1,2*2,2*3,2*4,2*5,2*6,2*8,2*9,,,,,,}
 *                 a
 *
 *               {3*1,3*2,3*3,3*4,3*5,3*6,3*8,3*9,,,,,,}
 *                 b
 *
 *               {5*1,5*2,5*3,5*4,5*5,5*6,5*8,5*9,,,,,,}
 *                 c
 *      第一个丑数为1，已经被被初始化了，下面我们求第二个丑数即dp[1]
 *      dp[1] = min(dp[0]*2,dp[0]*3,dp[0]*5) 即第一个丑数与2,3,5的乘积中最小的一个
 *      如果当前dp[0]*2 = dp[1] 说明当前a指向的是最小的，让a指针后移，依次分析其他两个
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 剑指Offer丑数 {
    public static void main(String[] args) {

    }

    /**
     * 动态规划的思想
     * @param n
     * @return
     */
    public static int nthUglyNumber1(int n) {
        // 定义三个指针 注意：每个集合都是严格单调递增的，但是集合之间却没有单调性
        int a = 0; // 指向2生成的丑数集合
        int b = 0; // 指向3生成的丑数集合
        int c = 0; // 指向5生成的丑数集合
        int[] dp = new int[n]; // 设置dp数组，dp[i]表示第i小的丑数
        dp[0] = 1; // 初始化
        for(int i = 1; i < n; i++) {
            // 每次将a，b，c指向的最小的元素就是当前第i个最小丑数，然后移动指针
            dp[i] = Math.min(Math.min(dp[a]*2,dp[b]*3),dp[c]*5);
            // 判断，然后移动指针
            if(dp[a]*2 == dp[i]) { // 表明当前a指向的元素是最小的，a移动
                a++;
            }
            if(dp[b]*3 == dp[i]) {
                b++;
            }
            if(dp[c]*5 == dp[i]) {
                c++;
            }
        }
        return dp[n-1];
    }

    /**
     * 利用队列求出
     * 思路分析；
     *   假设此时队列中有这些元素{1,2,3,4,5,}
     *   下面我们想要求出第6个丑数 x，
     *   x = min(1)
     *
     * @param n
     * @return
     */
    public static int nthUglyNumber2(int n) {
        if (n <= 5) {
            return n;
        }
        // 从n >= 6开始后面的丑数都是前面
        return -1;
    }

}
